/**
 * Copyright (c) 2008 - TheNittyGritty - Thomas Brekelmans
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package nl.thenittygritty.list.sorter
{
	import nl.thenittygritty.list.List;
	import nl.thenittygritty.list.ListIterator;
	import nl.thenittygritty.specification.ISpecification;	
	
	/**
	* Sorter can be used to sort a given list by several criteria. A criteria is made up of a Specification, which 
	* creates a sublist of items from a list. This sublist is then (optionally) sorted by a custom (Array based)
	* sorting method with optional sorting options. (See the Array.sort and Array.sortOn methods for more info on
	* the possibilities of Sorter.sort.
	* 
	* [:Tricky:]
	* This default sorter processes each item in the given list only once. As soon as an item in the list is satisfied
	* by a specification in an added criterion the item is removed from the list to ensure that the returned list has 
	* the same length as the original list and no item is listed under two different sublists/criteria.
	* If you would like to alter this behavior create a subclass of Sorter and override the sortListPerCriterion method.
	*/
	public class Sorter implements ISorter
	{
		// The list of criteria that define the way this sorter sorts the list.
		private var criteria:List;
		
		/**
		* Creates a new sorter instance.
		*/
		public function Sorter()
		{
			this.criteria = new List();
		}
		
		/**
		* Creates a criterion which is used to create sublist matching the given specification. This sublist is sorted with the givden sorting algorithm or sorting options.
		* 
		* @param specification The specification which creates a sublists of the list which is sorted by the sorter to which this criterion is added.
		* @param sortingAlgorithm An array sorting algorithm method which sorts the created sublists.
		* @param sortingOptions An array sorting option id such as Array.NUMERIC which is used instead of the sortingAlgorithm. See the array documentation for more info.
		*/
		public function addCriterion(specification:ISpecification, sortingAlgorithm:Function = null, sortingOptions:Number = 0):void
		{
			var criterion:Criterion = new Criterion(specification, sortingAlgorithm, sortingOptions);
			this.criteria.addItem(criterion);
		}
		
		/**
		* Sorts a given list into sublists according to the added criterion specification, each sublist is optionally sorted based on the corresponding criterion sorting algorithm and options.
		* 
		* @param list The list that will be sorted.
		*/
		public function sort(list:List):List
		{
			// Sort the list into sublists per criterion.
			var sortedList:List = this.sortListPerCriterion(list);
			
			// Check if any items are unproccessed and add these to the sortedList.
			sortedList = this.addRemainderOfOriginalList(sortedList, list);
			
			// Return the sorted list.
			return sortedList;
		}
		
		/**
		* Sorts a list into sublists and optionally sorts these, adds the sublists to a new list and returns that list (see class documentation tricky note for more info on this method).
		* 
		* @param list The list that will be sorted.
		*/
		private function sortListPerCriterion(list:List):List
		{
			// Create a new list in which the sorted items of list will be stored.
			var sortedList:List = new List();
			
			// Iterate in normal order over each criterion.
			var criteriaIterator:ListIterator = this.criteria.getIterator(List.LIST_ITERATOR) as ListIterator;
			for (criteriaIterator.rewind(); criteriaIterator.isValid(); criteriaIterator.next())
			{
				// Fill a temporary array with each item in the list that is satisfied by the specification of the current criterion. 
				var itemsSatisfiedByCriterion:Array = this.processListItemsForCriterion(criteriaIterator.getValue() as Criterion, list);
				
				// Sort the itemsSatisfiedByCriterion based on the current criterion sorting algorithm and sorting options.
				itemsSatisfiedByCriterion = this.sortItemsSatisfiedByCriterion(criteriaIterator.getValue() as Criterion, itemsSatisfiedByCriterion);
				
				// Loop through the itemsSatisfiedByCriterion.
				for (var i:int = 0; i < itemsSatisfiedByCriterion.length; ++i)
				{
					// Add it's data to the sorted list.
					sortedList.addItem(itemsSatisfiedByCriterion[i]);
					
					// And remove the processed item from the original list (to ensure that the returned list has the same length as the original list and no item is listed under two different sublists/criteria). 
					list.removeItem(itemsSatisfiedByCriterion[i]);
				}
			}
			
			// Return the sorted list.
			return sortedList;
		}
		
		/**
		* Returns an array to hold each item satisfied by the given criterion specification in the given list.
		* 
		* @param criterion The criterion whose specification each item in the list will be checked against.
		* @param list The list whose data will be checked against.
		*/
		private function processListItemsForCriterion(criterion:Criterion, list:List):Array
		{
			// Initialise a temporary array to hold each item satisfied by the criterion specification in the given list.
			var itemsSatisfiedByCriterion:Array = new Array();
			
			// Get a normal iterator for the given list.
			var listIterator:ListIterator = list.getIterator(List.LIST_ITERATOR) as ListIterator;
			// Iterate in normal order over each item in the list.
			for (listIterator.rewind(); listIterator.isValid(); listIterator.next())
			{
				// Retrieve the current item in the list.
				var listItem:* = listIterator.getValue();
				
				// See if the specification of the current criterion is satisfied by this item.
				if (criterion.getSpecification().isSatisfiedBy(listItem))
				{
					// If so, add it to the temporary array.
					itemsSatisfiedByCriterion.push(listItem);
				}
			}
			
			return itemsSatisfiedByCriterion;
		}
		
		/**
		* Sorts an array of items based on a sorting algorithm and the sorting options in the given criterion and returns the sorted items.
		* 
		* @param criterion The criterion whose sorting algorithm and sorting options are used to sort the items.
		* @param items The items that will be sorted.
		*/
		private function sortItemsSatisfiedByCriterion(criterion:Criterion, items:Array):Array
		{
			// If a sorting algorithm is defined.
			if (criterion.getSortingAlgorithm() != null)
			{
				// Sort the items with the provided sorting algorithm.
				items.sort(criterion.getSortingAlgorithm());
			}
			// Else if a sorting options id is defined.
			else if (criterion.getSortingOptions() != 0)
			{
				// Sort the items with the provided sorting options.
				items.sort(criterion.getSortingOptions());
			}
			
			return items;
		}
		/**
		* Checks if any items are unproccessed (i.e. did not match any criteria of the sorter) and adds these to the sortedList.
		* 
		* @param sortedList The sortedList of processed items.
		* @param list The original list that might contain remaining items that will be added to the sortedList.
		*/
		private function addRemainderOfOriginalList(sortedList:List, list:List):List
		{
			// If anything remains in the original list.
			if (list.getLength() > 0)
			{
				// Add it's items to the sorted list.
				sortedList = sortedList.concat(list);
			}
			
			return sortedList;
		}
		
		/**
		* Returns the name of the class in a String.
		*/
		public function toString():String
		{
			return "Sorter";
		}
	}
}